#include "gtree.h"
#include "Linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/*
1. 利用链表组织树的所有结点，但每个结点之间没有逻辑关系
2. 逻辑关系由parent和child链表连接起来
*/

/* 树结点结构体 */
typedef struct _tag_GTreeNode GTreeNode;
struct _tag_GTreeNode
{
  GTreeData* data;
  GTreeNode* parent;
  Linklist* child;
};

/* 链表结点结构体 */
typedef struct _tag_TLNode TLNode;
struct _tag_TLNode
{
  LinklistNode header;
  GTreeNode* node;
};

/* 静态打印函数，利用回调的思想 */ 
/**
 * @brief   把一个树结构给打印出来
 * @param   node：待打印的结点
 * @param   pFunc: 打印格式函数
 * @param   format: 表示整体缩进几个单位 
 * @param   gap: 结点与上下级之间的间隔(缩进)
 * @param   div: 分隔符
 * @retval
 * @note
 */
static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)
{
  int i = 0;

  if(node != NULL)
  {
    for(i=0; i<format; i++)
    {
      printf("%c", div);
    }
    // 先打印本节点的数据
    //printf("%c", (int)node->data);
    pFunc(node->data);
    
    printf("\n");
    // 再打印子节点的数据
    for(i=0; i<Linklist_Length(node->child); i++)
    {
      TLNode* trNode = (TLNode*)Linklist_Get(node->child, i);

      recursive_display(trNode->node, pFunc, format + gap, gap, div);
    }
  }
}

/**
 * @brief   删除树中结点所需要递归调用的函数
 * @param   list: 树结构链表
 * @param   node: 待删除的结点
 * @retval  None
 * @note
*/
static void recursive_delete(Linklist* list, GTreeNode* node)
{
  if((list != NULL) && (node != NULL))
  {
    GTreeNode* parent = node->parent;   // 待删除节点的父结点
    int index = -1;
    int i = 0;

    for(i=0; i<Linklist_Length(list); i++)
    {
      TLNode* trNode = (TLNode*)Linklist_Get(list, i);
      // 在所有树结点中找到待删除的结点  
      if(trNode->node == node)
      {
        Linklist_Delete(list, i);     // 删除操作
        free(trNode);
        index = i;
        break;
      }
    }

    if(index >= 0)      // 如果不是根结点
    {
      if(parent != NULL)  // 待删除的结点的父结点不为空
      {
        for(i=0; i<Linklist_Length(parent->child); i++)
        {
          TLNode* trNode = (TLNode*)Linklist_Get(parent->child, i);
          // 在其子结点中寻找待删除的结点  
          if(trNode->node == node)
          {
            Linklist_Delete(parent->child, i);
            free(trNode);
            break;
          }          
        }
      }
      // 该结点的子结点全部删除
      while(Linklist_Length(node->child) > 0)
      {
        TLNode* trNode = (TLNode*)Linklist_Get(node->child, 0);
        recursive_delete(list, trNode->node);   // 递归
      }

      Linklist_Destroy(node->child);

      free(node);
    }
  }
}

/* 求树高度所调用的递归函数 */
static int recursive_height(GTreeNode* node)
{
  int ret = 0;

  if(node != NULL)
  {
    int subHeight = 0;
    int i = 0;

    for(i=0; i<Linklist_Length(node->child); i++)
    {
      TLNode* trNode = (TLNode*)Linklist_Get(node->child, i);

      subHeight = recursive_height(trNode->node);
      // 挑出高度最大指
      if(ret < subHeight)
      {
        ret = subHeight;
      }
    }

    ret = ret + 1;    // 加上自身
  }
}

/* 求树的度数所调用的递归函数 */
static int recursive_degree(GTreeNode* node)
{
  int ret = -1;

  if(node != NULL)
  {
    int subdegree = 0;
    int i = 0;
    // 子结点链表的长度
    ret = Linklist_Length(node->child);
    for(i=0; i<Linklist_Length(node->child); i++)
    {
      TLNode* trNode = (TLNode*)Linklist_Get(node->child, i);

      subdegree = recursive_degree(trNode->node);

      if(ret < subdegree)
      {
        ret = subdegree;
      }
    }
  }

  return ret;
}

/* 创建一个链式的树结构 */
GTree* GTree_Create()
{
  return Linklist_Create();
}

void GTree_Destroy(GTree* tree)
{
  GTree_Clear(tree);
  Linklist_Destroy(tree);
}

void GTree_Clear(GTree* tree)
{
  GTree_Delete(tree, 0);
}

/* pos表示父结点的位置 */
int GTree_Insert(GTree* tree, GTreeData* data, int pos)
{
  Linklist* list = (Linklist*)tree;
  // 合法性判断
  int ret = (list != NULL) && (data != NULL) && (pos < Linklist_Length(list));

  if(ret)
  {
    GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));
    TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));
    TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));
    TLNode* pNode = (TLNode*)Linklist_Get(list, pos);   // 父结点位置

    ret = (cNode != NULL) && (trNode != NULL) && (cldNode != NULL); 

    if(ret)
    {
      cNode->data = data;
      cNode->parent = NULL;     // 先暂时指定没有双亲
      cNode->child = Linklist_Create();
      // 一个结点会在两个链表中
      trNode->node = cNode;
      cldNode->node = cNode;

      Linklist_Insert(list, (LinklistNode*)trNode, Linklist_Length(list));
      if(pNode != NULL)
      {
         cNode->parent = pNode->node;
         Linklist_Insert(pNode->node->child, (LinklistNode*)cldNode, Linklist_Length(pNode->node->child)); 
      }
    }
    else    // 根结点为空，没有子结点，不需要插入操作
    {
      free(cldNode);   
      free(trNode);
      free(cNode);
    }
  }
  return ret;
}

/**
 * @brief   删除pos位置处的结点及其子结点
 * @param   tree: 待操作的树
 * @param   pos: 待删除结点的位置
 * @retval  返回待删除的结点的数据域指针
 * @note    递归操作
*/
GTreeData* GTree_Delete(GTree* tree, int pos)
{
  TLNode* trNode = (TLNode*)Linklist_Get(tree, pos);
  GTreeData* ret = NULL;

  if(trNode != NULL)
  {
    ret = trNode->node->data;   // 返回待删除的结点的数据域指针

    recursive_delete(tree, trNode->node);
  }

  return ret;
}

/* 返回pos位置处结点的数据域内容 */
GTreeData* GTree_Get(GTree* tree, int pos)
{
  TLNode* trNode = (TLNode*)Linklist_Get(tree, pos);
  GTreeData* ret = NULL;
  
  if(trNode != NULL)
  {
    ret = trNode->node->data;
  }
  
  return ret;
}

/* 获取树的根结点 */
GTreeData* GTree_Root(GTree* tree)
{
  return GTree_Get(tree, 0);
}

/* 求树的高度 */
int GTree_Height(GTree* tree)
{
  TLNode* trNode = (TLNode*)Linklist_Get(tree, 0);
  int ret = 0;

  if(trNode != NULL)
  {
    ret = recursive_height(trNode->node);
  }

  return ret;
}

/* 树用链表表示的长度 */
int GTree_Count(GTree* tree)
{
  return Linklist_Length(tree);
}

/* 求树的度数 */
int GTree_Degree(GTree* tree)
{
  TLNode* trNode = (TLNode*)Linklist_Get(tree, 0);
  int ret = -1; 

  if(trNode != NULL)
  {
     ret = recursive_degree(trNode->node); 
  } 

  return ret;
}

/* 树结构显示 */
void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)
{
  TLNode* trNode = (TLNode*)Linklist_Get(tree, 0);

  if(trNode != NULL)
  {
    recursive_display(trNode->node,  pFunc, 0, gap, div);
  }
}
